It is well settled that the MAP (Maximum A posterior Probability) decoding scheme, which is the maximum a posterior probability decoding method, is presently the best soft output decoding algorithm used in decoding of turbo code. Further, there is a case where, for implementation of the circuit, the Max-log-MAP scheme is used. The Max-log-MAP scheme is similar to the MAP scheme to which log calculation is applied. As a soft decision decoding method for convolution code used inside a turbo decoder, Max-log-MAP and SOYA (Soft Output Viterbi Algorithm) are known to require a comparatively small amount of operation.
However, turbo decoding still requires a large amount of operation compared to other codes, and further reduction in the amount of operation is demanded.
FIG. 1 is a block diagram showing a decoder for describing a conventional Max-log-MAP decoding method.
In FIG. 1, decoder 1 is configured with γα calculating section 11, timing adjusters 12 and 13, γβ calculating section 14 and Λ calculating section 15. Λ calculating section 15 is composed of likelihood calculating sections 16 and 17 and subtractor 18.
There are three types of data sequences, systematic s(n), parity p(n) and a priori value e(n), inputted to Max-log-MAP decoder 1. Here, n=0 to K−1 hold, and K is a “block size (i.e. the number of transmission information bits).”
Max-log-MAP decoder 1 finds a soft output value Λ(n) from a received sequence y (including vectors s and p) and vector e of an extrinsic value. Λ(n) is also referred to as a “posteriori value” and is a log likelihood ratio (LLR) of transmission bits estimated by decoder 1. That is, Λ(n) is defined as in following equation 1, and, if Λ(n)>0, transmission data d(n) of the n-th bit is estimated “0” and, if Λ(n)<0, d(n) is estimated “1.” Further, the operation of acquiring the estimated value d by deciding the sign of LLR is referred to as “hard decision processing.”
                    (                  Equation          ⁢                                          ⁢          1                )                                                                                      ⁢                              Λ            ⁡                          (              n              )                                =                      log            ⁢                                          p                ⁡                                  (                                                            d                      ⁡                                              (                        n                        )                                                              =                                          0                      ❘                      y                                                        )                                                            p                ⁡                                  (                                                            d                      ⁡                                              (                        n                        )                                                              =                                          1                      ❘                      y                                                        )                                                                                        [        1        ]            
FIG. 2 is a block diagram of turbo decoder 20 using Max-log-MAP decoder 1 as a constituent decoder.
With this example, two Max-log-MAP decoders 1 (hereinafter, “constituent decoders”) of FIG. 1 are used. Turbo decoder 20 is composed of two constituent decoders 21 and 22 (Max-log-MAP decoders 1 and 2), adders 23 and 24, interleavers 25 and 26 (interleavers π), deinterleavers 27 and 28 (deinterleaver π−1) and sign decider 29 (sign). The interleavers π and deinterleavers π−1 are circuits for rearranging the order of data according to a predetermined method.
Max-log-MAP decoder 21 receives as input systematic s, first parity p1 and the extrinsic value e1 transmitted from Max-log-MAP decoder 22, and outputs Λ1 which is the first LLR.
As shown in following equation 2, a new extrinsic value e1′ is determined by subtracting systematic s and the extrinsic value e1 from Λ1.e1′(n)=Λ1(n)−(s(n)+e1(n))  (Equation 2)
(e2) obtained by interleaving e1′, is used as an extrinsic value to input to Max-log-MAP decoder 22. Further, data obtained by interleaving systematic s and second parity p2 are inputted to Max-log-MAP decoder 22.
Based on these inputs, Max-log-MAP decoder 22 outputs Λ2 which is a second LLR. Similarly, as shown in following equation 3, a new extrinsic value e2′ is calculated by subtracting inputted systematic s(π(n)) interleaved and the extrinsic value e2 from Λ2.e2′(n)=Λ2(n)−(s(π(n))+e2(n))  (Equation 3)
An input obtained by deinterleaving this new extrinsic value e2′ is used as a new input to Max-log-MAP decoder 21. Deinterleaving refers to “reverse rearrangement processing” corresponding to the above interleaving.
Accuracies of Λ1 and Λ2 are improved by repeating the above processings. The estimated value d^ of the transmission bits can be acquired by carrying out a sufficient number of times of repetitions, then deciding the sign of Λ2 and carrying out deinterleaving.
Next, the detailed functions of Max-log-MAP decoding will be described. Here, all the following equations are used to decode turbo code disclosed in Non-Patent Document 1 and are only shown as examples. Generally, the following equations may be different respectively.
The α, β and γ in Max-log-MAP decoding include the following meanings. That is,
α: a total of likelihoods of a path reaching a certain state
β: a total of likelihoods of a path beyond a certain state
γ: likelihoods of branches.
(1) γ Calculation
γ calculation is carried out prior to α calculation and β calculation.
The following four γ's shown in following equation 4 are calculated from the n-th bit input values s (n), p (n), and e (n).γ00(n)=(s(n)+e(n)+p(n))/2γ01(n)=(s(n)+e(n)−p(n))/2γ10(n)=(−s(n)−e(n)+p(n))/2γ11(n)=(−s(n)−e(n)−p(n))/2  (Equation 4)(2) α Calculation
α is calculated according to the recurrence equation shown in following equation 5 using γ's determined as described above.α0(n+1)=min{α0(n)+γ00(n),α4(n)+γ11(n)}α1(n+1)=min{α4(n)+γ00(n),α0(n)+γ11(n)}α2(n+1)=min{α1(n)+γ5(n),α5(n)+γ10(n)}α3(n+1)=min{α5(n)+γ01(n),α1(n)+γ10(n)}α4(n+1)=min{α2(n)+γ01(n),α6(n)+γ10(n)}α5(n+1)=min{α6(n)+γ01(n),α2(n)+γ10(n)}α6(n+1)=min{α3(n)+γ00(n),α7(n)+γ11(n)}α7(n+1)=min{α7(n)+γ00(n),α3(n)+γ11(n)}  (Equation 5)
In above equation 5, min{a, b} represents an operation of selecting a smaller candidate from two candidates a and b. The initial value of the α is α0=0 and αi(0)=+∞(i>0). Further, the α is calculated from the smallest value of n to the largest value of n (i.e. in ascending order), and is referred to as a “forward probability.”
(3) β Calculation
Similarly, the β is calculated according to the recurrence equation of following equation 6 using the γ.β0(n)=min{β0(n+1)+γ00(n),β1(n+1)+γ11(n)}β1(n)=min{β2(n+1)+γ01(n),β3(n+1)+γ10(n)}β2(n)=min{β5(n+1)+γ01(n),β4(n+1)+γ10(n)}β3(n)=min{β7(n+1)+γ00(n),β6(n+1)+γ11(n)}β4(n)=min{β1(n+1)+γ00(n),β0(n+1)+γ11(n)}β1(n)=min{β2(n+1)+γ01(n),β3(n+1)+γ10(n)}β5(n)=min{β3(n+1)+γ01(n),β2(n+1)+γ10(n)}β6(n)=min{β4(n+1)+γ01(n),β5(n+1)+γ10(n)}β7(n)=min{β6(n+1)+γ00(n),β7(n+1)+γ11(n)}  (Equation 6)
Further, the β is calculated from the largest value of n to the smallest value of n (i.e. in descending order). γ calculation carried out prior to β calculation is carried out according to the flow of β calculation. Then, s, p and e are rearranged by a FILO (First-In Last-Out) buffer and inputted to γ calculating section 14a. Further, the β is referred to as the “backward probability.”
(4) Λ calculation
In Λ calculation, log likelihoods λ0(n) and λ1(n) are determined per bit using following equations 7 and 8. The difference between these is the log likelihood ratio (LLR) Λ(n) shown in following equation 9.
                    (                  Equation          ⁢                                          ⁢          7                )                                                                                      ⁢                              λ            ⁡                          (              n              )                                =                      min            ⁢                          {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    α                                                    0                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      β                                                    0                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      γ                                                    00                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                                                                                                                α                                                    1                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      β                                                    2                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      γ                                                    01                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                                                                                                                α                                                    2                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      β                                                    5                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      γ                                                    01                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                                                                                                                α                                                    3                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      β                                                    7                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      γ                                                    00                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  α                                              4                                                                                        ⁡                                                                                          (                                              n                                              )                                                                                                                                +                                                                                                                                    β                                              1                                                                                        ⁡                                                                                          (                                              n                                              )                                                                                                                                +                                                                                                                                    γ                                              00                                                                                        ⁡                                                                                          (                                              n                                              )                                                                                                                                                                      ,                                                                                                                                                                                                                                                                                                                                                                                                                                                    α                                        5                                                                            ⁡                                                                              (                                        n                                        )                                                                                                              +                                                                                                                  β                                        3                                                                            ⁡                                                                              (                                        n                                        )                                                                                                              +                                                                                                                  γ                                        01                                                                            ⁡                                                                              (                                        n                                        )                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                      α                                  6                                                                ⁡                                                                  (                                  n                                  )                                                                                            +                                                                                                β                                  4                                                                ⁡                                                                  (                                  n                                  )                                                                                            +                                                                                                γ                                  01                                                                ⁡                                                                  (                                  n                                  )                                                                                                                      ,                                                                                                                                                                                                                                                            α                          7                                                ⁡                                                  (                          n                          )                                                                    +                                                                        β                          6                                                ⁡                                                  (                          n                          )                                                                    +                                                                        γ                          00                                                ⁡                                                  (                          n                          )                                                                                                                                }                                                          [        2        ]                                (                  Equation          ⁢                                          ⁢          8                )                                                                                      ⁢                                            λ              1                        ⁡                          (              n              )                                =                      min            ⁢                          {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    α                                                    0                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      β                                                    1                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      γ                                                    11                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                                                                                                                α                                                    1                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      β                                                    3                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      γ                                                    10                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                                                                                                                α                                                    2                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      β                                                    4                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      γ                                                    10                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                                                                                                                α                                                    3                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      β                                                    6                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                  +                                                                                                                                                      γ                                                    11                                                                                                    ⁡                                                                                                      (                                                    n                                                    )                                                                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  α                                              4                                                                                        ⁡                                                                                          (                                              n                                              )                                                                                                                                +                                                                                                                                    β                                              0                                                                                        ⁡                                                                                          (                                              n                                              )                                                                                                                                +                                                                                                                                    γ                                              11                                                                                        ⁡                                                                                          (                                              n                                              )                                                                                                                                                                      ,                                                                                                                                                                                                                                                                                                                                                                                                                                                    α                                        5                                                                            ⁡                                                                              (                                        n                                        )                                                                                                              +                                                                                                                  β                                        2                                                                            ⁡                                                                              (                                        n                                        )                                                                                                              +                                                                                                                  γ                                        10                                                                            ⁡                                                                              (                                        n                                        )                                                                                                                                              ,                                                                                                                                                                                                                                                                                                                                                                      α                                  6                                                                ⁡                                                                  (                                  n                                  )                                                                                            +                                                                                                β                                  5                                                                ⁡                                                                  (                                  n                                  )                                                                                            +                                                                                                γ                                  10                                                                ⁡                                                                  (                                  n                                  )                                                                                                                      ,                                                                                                                                                                                                                                                            α                          7                                                ⁡                                                  (                          n                          )                                                                    +                                                                        β                          7                                                ⁡                                                  (                          n                          )                                                                    +                                                                        γ                          11                                                ⁡                                                  (                          n                          )                                                                                                                                }                                                                                          (                  Equation          ⁢                                          ⁢          9                )                                                                                      ⁢                              Λ            ⁡                          (              n              )                                =                                                    λ                1                            ⁡                              (                n                )                                      -                                          λ                0                            ⁡                              (                n                )                                                                                    
In λ calculation, α value is calculated using both α and β. The α is calculated in ascending order of n and the β is calculated in descending order of n, and so the α or β needs to be rearranged and used.
In FIG. 1, the α is rearranged by the FILO buffer and the λ is calculated sequentially from the largest value of n to the smallest value of n.
FIG. 3 is a flowchart of Max-log-MAP decoding and, in this figure, ST refers to each “step” in the flowchart. This flow is executed appropriately when the α and β are calculated. Further, the description of y calculation is omitted.
First, α(n) is calculated for n=0 to K−1 in steps ST1 and ST2. Here, calculation of α(n) means calculating eight values of α0(n) to α7(n). Calculated α(n) is stored in timing adjuster (i.e. FILO memory) 12.
Next, β(n) is calculated for n=K−1 to 0, insteps ST3 and ST4. After β(n) is calculated, λ0(n) and λ1(n) are calculated in step ST5 and Λ(n) is calculated in step ST6. α(n) stored in timing adjuster 12 is used to calculate λ0(n) and λ1(n). While the α is calculated in order from 0 to K−1, the λ is calculated in order from K−1 to 0, and so the timing adjuster is used.
Further, β calculation, λ calculation and Λ calculation are often pipelined. That is, while λ0(n) and λ1(n) are calculated, β(n−1) is calculated. Then, soon after calculation of λ0(n) and λ1(n) is finished, calculation of λ0(n−1) and λ1(n−1) can be started.    Patent Document 1: Japanese Patent Application Laid-Open No. 2000-278144    Non-Patent Document 1: “A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain,” Robertson, P., Villebrun, E., Hoeher, P., IEEE International Conference on Communications, 1995. Page(s): 1009-1013 vol. 2    Non-Patent Document 2: 3GPP TS 25.212 v6.3.0